package com.wu.getnext;

/**
 * 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
 * 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
 */
class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null){
            return null;
        }
        //如果该节点存在右子树,则下个节点为右子树，其实是找到它的右子树的最左孩子，一直遍历。
        if (pNode.right != null){
            return getLeft(pNode);
        }else {
            //如果该节点不存在右子树，则需分两种情况
            //该节点的父节p，p为其父节点的左子树,不符合，则一直找其父节点
            while (pNode.next != null && pNode.next.left != pNode){
                pNode = pNode.next;
            }
            //符合条件则返回
            return pNode.next;
        }


    }
    public TreeLinkNode getLeft(TreeLinkNode node){
        TreeLinkNode cur = node.right;
        while (cur.left != null){
            cur = cur.left;
        }
        return cur;
    }
}